There are many applications where computations are performed using finite field operations. In cryptography, e.g. public key cryptography, operations such as multiplication or exponentiation of elements in some group Zn may be required, where modular arithmetic is used to operate on the integers, or possibly on polynomials taken modulo some reduction polynomial, such as when computing in an extension of a finite field. A particular class of groups used increasingly in cryptography are elliptic curve groups, which are a tuples of elements in an underlying field that satisfy the equation of an elliptic curve.
Many operations in such groups require reduction. For example, modular arithmetic is used when multiplying two numbers modulo some number n. The classical approach to this type of operation is to first perform the multiplication and then calculate the remainder of the product modulo some number n. The calculation of the remainder is referred to as reduction.
The classical approach to reduction is well known in the art. Although it is simple for basic operations such as in multi-precision calculations and does not require precomputation, the classical method of calculating the remainder is considered slow, due to the process of classical modular reduction being computationally equivalent to dividing two numbers.
Alternative methods of modulus reduction are known. For example, the American National Standards Institute outlines in the document “X9.62:1998 Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), 1998” methods for efficient high-to-low reduction of large integers.
It is also possible to obtain efficiencies by selection of the finite field group that is used. The National Institute for Standards and Technology (NIST) defines elliptic curves in the document “Recommended elliptic curves for Federal Government use, 1999” and lists word aligned primes that have non-zero bit values at word boundaries. Typically, these primes have a representation that has −1, +1 on 32-bit boundaries, which simplifies modular computation. The book “Guide to Elliptic Curve Cryptography, Springer Verlag, 2004” by Hankerson et al. provides techniques using such special form primes to yield efficient high-to-low reduction algorithms. In general, simple word aligned equivalents for higher order components are substituted in terms of its lower-order components. However, it is still necessary to reduce that final result modulo by some number n. Moreover, high-to-low modulus reduction methods must deal with carries that appear from below as the reduction proceeds.
A more efficient form of reduction is known as Montgomery reduction. Montgomery reduction is described in “Handbook of Applied Cryptography, CRC Press, 1997” by Menezes et al. This method relies on performing certain precomputations to allow many calculations to be done faster. For example, if A is the product of two integers and is to be reduced mod n, then to obtain a Montgomery reduction modulo n, to the extent R, a multiple m of n is added to A so that A+mn≡0 (mod R). The multiple m is calculated using m≡μA (mod R), where μ=(−1/n) (mod R) and is precalculated and stored.
Using Montgomery reduction, low-order components are reduced instead of high-order components. This low-to-high reduction is convenient and efficient as it follows the natural flow of carries in the reduced component. Montgomery reduction also benefits from the fact that the steps of multiplication and shifting are generally faster than division on most computing machines.